package leetcode_1_200;

import jdk.nashorn.internal.runtime.ListAdapter;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeeCode_139_timeout {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
//        System.out.println(wordBreak("leetcode", list));
        List<String> list2 = new ArrayList<>();
        list2.add("apple");
        list2.add("pen");
//        System.out.println(wordBreak("applepenapple", list2));
        List<String> list3 = new ArrayList<>();
        list3.add("cats");
        list3.add("dog");
        list3.add("sand");
        list3.add("and");
        list3.add("cat");
//        System.out.println(wordBreak("catsandog", list3));
        List<String> list4 = new ArrayList<>();
        list4.add("aa");
        list4.add("aaa");
        list4.add("aaaa");
        list4.add("aaaa");
        list4.add("aaaaa");
        list4.add("b");
        System.out.println(wordBreak("aaaaaaaaaaaaaaaab", list4));

    }
    private static boolean wordBreak(String s, List<String> wordDict) {
        Map<Character, List<String>> table = new HashMap<>();
        for (String str : wordDict) {
            char c = str.charAt(0);
            if (table.containsKey(c)){
                boolean flag = true;
                List<String> list = table.get(c);
                for (int i = 0; i < list.size(); i++) {
                    String sms = list.get(i);
                    if (str.length() % sms.length() == 0){
                        String tms = "";
                        for (int j = 0; j < str.length() / sms.length(); j++) {
                            tms += sms;
                        }
                        if (tms.equals(str)){
                            flag = false;
                            break;
                        }
                    }
                }
                if (flag)
                    list.add(str);
            }else {
                ArrayList<String> list = new ArrayList<>();
                list.add(str);
                table.put(c, list);
            }
        }
        return f(s, table);
    }
    private static boolean f(String s, Map<Character, List<String>> table){
        char c = s.charAt(0);
        if (!table.containsKey(c))
            return false;
        List<String> list = table.get(c);
        for (String str : list) {
            int len = str.length();
            if (s.length() < len)
                continue;
            if (s.length() == len){
                if (s.equals(str)){
                    return true;
                }
                continue;
            }
            String pre = s.substring(0, len);
            if (str.equals(pre)){
                if(f(s.substring(len), table))
                    return true;
            }
        }
        return false;
    }
}
